Lecture 15

这一节要讲ACM里面经典的博弈。

博弈的元素：

• 两个玩家
• perfect information
• 有限的步数，使得游戏结束
• 三种结果：赢，输，平局

井字棋是一个会平局的游戏。

感觉这节课使用归纳法来讲经典博弈不是很好，还是用必胜必败态来解释比较的清晰易懂。

移石子游戏

n堆石子，每堆m个。最后移除石子的玩家输掉了比赛。

另一个游戏

讲了纳什均衡和backward induction推导出来的结果的一致性。